/**
 * Вспомогательный класс для хранения информации о родителях
 * и потомках элемента в дереве.
 */

#ifndef _TREENODE_H
#define	_TREENODE_H

#include <list>
#include <algorithm>
#include "Tree.h"
#include "common/TreeAllocator.h"
#include "common/IllegalArgumentException.h"
#include "common/NullPointerException.h"

namespace etu {
namespace tree {

template <typename T> class Tree;

template <typename T>
class TreeNode {

public:
    typedef class common::TreeAllocator<TreeNode<T> *> Allocator;
    typedef typename std::list<TreeNode<T> *, Allocator > NodeList;
    typedef typename NodeList::iterator NodeListIterator;

private:

    T value;
    NodeList* parents;
    NodeList* childs;
    
public:

    /**
     * Конструктор копирования.
     * Происходит поверхностное копирование списков родителей и потомков дерева.
     */
    TreeNode(const TreeNode& orig) {
    	NodeListIterator it;

        for(it = orig.parents->begin(); it != orig.parents->end(); it++) {
            this->parents->push_back((* it));
        }

        for(it = orig.childs->begin(); it != orig.childs->end(); it++) {
            this->childs->push_back((* it));
        }

        this->value = orig.value;
    }

    /**
     * Деструктор. Удаляются все родители и потомки,
     * которые невозможно посетить после удаления данного узла
     */
    ~TreeNode() {
        //
    }

    bool hasChild(TreeNode<T>* child) const {
        bool ret = false;
        NodeListIterator it;

        for(it = this->childs->begin(); it != this->childs->end(); it++) {
            if((* it) == child) {
                ret = true;
                break;
            }
        }

        return ret;
    }

    /**
     * Проверка, имеет ли данный узел потомка с заданным значением
     * @param value значение узла-потомка
     * @return true, если имеет; иначе false
     */
    bool hasChild(const T& value) {
        bool ret = false;
        NodeListIterator it;

        for(it = this->childs->begin(); it != this->childs->end(); it++) {
            TreeNode<T>* node = (* it);

            if(node->getValue() == value) {
                ret = true;
                break;
            }
        }

        return ret;
    }

    bool hasParent(TreeNode<T>* parent) const {
        bool ret = false;
        NodeListIterator it;

        for(it = this->parents->begin(); it != this->parents->end(); it++) {
            if((* it) == parent) {
                ret = true;
                break;
            }
        }

        return ret;
    }

    /**
     * Проверка, имеет ли данный узел родителя с заданным значением
     * @param value значение узла-родителя
     * @return true, если имеет; иначе false
     */
    bool hasParent(const T& value) {
        bool ret = false;
        NodeListIterator it;

        for(it = this->parents->begin(); it != this->parents->end(); it++) {
            TreeNode<T>* node = (* it);

            if(node->getValue() == value) {
                ret = true;
                break;
            }
        }

        return ret;
    }

    /**
     * Получение узлов-потомков данного узла
     * @return список указателей на узлы-потомки данного узла
     */
    NodeList* getChilds() const {
    	NodeList* ret = new NodeList();
    	NodeListIterator it;

        for(it = this->childs->begin(); it != this->childs->end(); it++) {
            ret->push_back((* it));
        }

        return ret;
    }

    /**
     * Получение количества потомков для данного узла
     * @return количество потомков для данного узла
     */
    int getChildsCount() const {
        return this->childs->size();
    }

    /**
     * Получение значений узлов-потомков данного узла
     * @return указатель на список значений узлов-потомков данного узла.
     * после использования нужно освободить память, занимаемую им
     */
    std::list<T>* getChildValues() const {
        std::list<T>* ret = new std::list<T>();
        NodeListIterator it;

        for(it = this->childs->begin(); it != this->childs->end(); it++) {
            TreeNode<T>* node = (* it);
            ret->push_back(node->getValue());
        }

        return ret;
    }

    /**
     * Получение значений узлов-родителей данного узла
     * после использования нужно освободить память, занимаемую им
     * @return указатель на список значений узлов-родителей данного узла.
     */
    NodeList* getParents() const {
    	NodeList* ret = new NodeList();
        NodeListIterator it;

        for(it = this->parents->begin(); it != this->parents->end(); it++) {
            ret->push_back((* it));
        }

        return ret;
    }

    /**
     * Получение количества родителей для данного узла
     * @return количество родителей для данного узла
     */
    int getParentsCount() const {
        return this->parents->size();
    }

    /**
     * Получение значений узлов-родителей данного узла
     * @return указатель на список значений узлов-родителей данного узла.
     * после использования нужно освободить память, занимаемую им
     */
    std::list<T>* getParentValues() const {
        std::list<T>* ret = new std::list<T>();
        NodeListIterator it;

        for(it = this->parents->begin(); it != this->parents->end(); it++) {
            TreeNode<T>* node = (* it);
            ret->push_back(node->getValue());
        }

        return ret;
    }

    /**
     * Добавление узла в список узлов-потомков для данного дерева
     * @param child узел, который нужно добавить в список потомков данного узла
     * @return false, если узел-потомок уже был ранее добавлен; иначе true
     * @throws NullPointerException если узел-потомок не задан
     */
    bool addChild(TreeNode<T>* child) throw(common::NullPointerException) {
        if(child == NULL) {
            throw common::NullPointerException("Данные о потомке должны быть заданы");
        }

        bool ret = false;

        if(!this->hasChild(child)) {
            this->childs->push_back(child);
            child->addParent(this);
            ret = true;
        }

        return ret;
    }

    /**
     * Добавление нового потомка для данного узла
     * @param value значение нового узла-потомка
     * @return false, если узел-потомок уже был ранее добавлен; иначе true
     */
    bool addChild(const T& value) {
        bool ret = false;

        if(!this->hasChild(value)) {
            TreeNode<T>* node = TreeNode<T>::newChildNode(this, value);
            this->childs->push_back(node);
            ret = true;
        }

        return ret;
    }

    bool removeChild(TreeNode<T>* child) {
    	if(child == NULL) {
			throw common::IllegalArgumentException("Данные о потомке должны быть заданы");
		}

        bool ret = false;
        NodeListIterator it;

        for(it = this->childs->begin(); it != this->childs->end(); it++) {
            if((* it) == child) {
                this->childs->erase(it);
                child->parents->remove(this);

                break;
            }
        }

        return ret;
    }

    /**
     * Удаление узла-потомка, имеющего заданное значение
     * @param value значение удаляемого узла-потомка
     * @return false, если узел-потомок с заданным значением не существует; иначе true
     */
    bool removeChild(const T& value) {
        bool ret = false;
        NodeListIterator it;

        for(it = this->childs->begin(); it != this->childs->end(); it++) {
            TreeNode<T>* node = (* it);

            if(node->value == value) {
                this->childs->erase(it);
                node->parents->remove(this);

//                if(node->parents->size() == 0) {
//                    delete node;
//                }

                ret = true;
                break;
            }
        }

        return ret;
    }

    bool removeParent(TreeNode<T>* parent) {
    	if(parent == NULL) {
			throw common::IllegalArgumentException("Данные о родителе должны быть заданы");
		}

        bool ret = false;
        NodeListIterator it;

        for(it = this->parents->begin(); it != this->parents->end(); it++) {
            if((* it) == parent) {
                this->parents->erase(it);
                parent->childs->remove(this);

                break;
            }
        }

        return ret;
    }

    /**
     * Удаление узла-родителя, имеющего заданное значение
     * @param value значение удаляемого узла-родителя
     * @return false, если узел-родитель с заданным значением не существует; иначе true
     */
    bool removeParent(const T& value) {
        bool ret = false;
        NodeListIterator it;

        for(it = this->parents->begin(); it != this->parents->end(); it++) {
            TreeNode<T>* node = (* it);

            if(node->value == value) {
                this->parents->erase(it);
                node->childs->remove(this);

//                if(node->childs->size() == 0) {
//                    delete node;
//                }

                ret = true;
                break;
            }
        }

        return ret;
    }

    /**
     * Задание нового значения элемента для данного узла
     * @param value новое значение для данного узла
     */
    void setValue(const T& value) {
        this->value = value;
    }

    /**
     * Получение значения элемента для данного узла
     */
    T getValue() const {
        return this->value;
    }

    /**
     * Добавление узла в список узлов-родителей для данного дерева
     * @param child узел, который нужно добавить в список родителей данного узла
     * @return false, если узел-родитель уже содержится в списке; иначе true
     * @throws NullPointerException если узел-родитель не задан
     */
    bool addParent(TreeNode<T>* parent) throw(common::NullPointerException) {
        if(parent == NULL) {
            throw common::NullPointerException("Данные о родителе должны быть заданы");
        }

        bool ret = false;

        if(!this->hasParent(parent)) {
            this->parents->push_back(parent);
            parent->addChild(this);
            ret = true;
        }

        return ret;
    }

    /**
     * Добавление нового родителя для данного узла
     * @param value значение нового узла-родителя
     * @return false, если узел-родитель уже был ранее добавлен; иначе true
     */
    bool addParent(const T& value) {
        bool ret = false;

        if(!this->hasParent(value)) {
            TreeNode<T>* node = TreeNode<T>::newParentNode(this, value);
            this->parents->push_back(node);
            ret = true;
        }

        return ret;
    }

    /**
     * Создание полной копии данного узла.
     * Полное копирование (deep copy) производится для всех элементов,
     * кроме узла, указанного как первого родителя или потомка для данного узла
     * @param previous первый узел-родитель или узел-потомок,
     * от которого был создан данный узел
     * @return полная копия данного узла
     */
    TreeNode<T>* clone(TreeNode<T>* previous = NULL) {
        TreeNode<T>* ret = TreeNode<T>::newRootNode(this->value);
        NodeListIterator it;

        for(it = this->parents->begin(); it != this->parents->end(); it++) {
            TreeNode<T>* node = (* it);

            if(previous != NULL) {
                T previousValue = previous->getValue();
                T nodeValue = node->getValue();

                if(previousValue != nodeValue) {
                    ret->addParent(node->clone(ret));
                }
            } else {
                ret->addParent(node->clone(ret));
            }
        }

        for(it = this->childs->begin(); it != this->childs->end(); it++) {
            TreeNode<T>* node = (* it);

            if(previous != NULL) {
                T previousValue = previous->getValue();
                T nodeValue = node->getValue();

                if(previousValue != nodeValue) {
                    ret->addChild(node->clone(ret));
                }
            } else {
                ret->addChild(node->clone(ret));
            }
        }

        return ret;
    }

    /**
     * Создание корневого узла дерева
     * @param tree дерево, для которого будет создан корневой узел
     * @param value значение элемента данного узла
     */
    static TreeNode<T>* newRootNode(const T& value) {
        return new TreeNode<T>(value);
    }

    /**
     * Создание родителя для заданного узла
     * @param child узел-потомок, для которого создаётся данный узел-родитель
     * @param value значение элемента данного узла
     */
    static TreeNode<T>* newParentNode(TreeNode<T>* child, const T& value) 
        throw(common::IllegalArgumentException) {
        
        if(child == NULL) {
            throw common::IllegalArgumentException("Данные о потомке должны быть заданы");
        }

        TreeNode<T>* ret = new TreeNode<T>(value);
        ret->childs->push_back(child);
        return ret;
    }

    /**
     * Создание потомка для заданного узла
     * @param parent узел-родитель, для которого создаётся данный узел-потомок
     * @param value значение элемента для данного узла
     */
    static TreeNode<T>* newChildNode(TreeNode<T>* parent, const T& value) 
        throw (common::IllegalArgumentException) {
        
        if(parent == NULL) {
            throw common::IllegalArgumentException("Данные о родителе должны быть заданы");
        }

        TreeNode<T>* ret = new TreeNode<T>(value);
        ret->parents->push_back(parent);
        return ret;
    }

private:

    /**
     * Создание узла с заданным значением для заданного дерева
     * @param value значение элемента для создаваемого узла
     */
    TreeNode(const T& value) {
        this->value = value;
        this->parents = new NodeList();
        this->childs = new NodeList();
    }
};

}
}

#endif	/* _TREENODE_H */

